CNR Author
operator:
and / or
Typology
operator:
and / or
Language
operator:
and / or
Date
operator:
and / or
Rights
operator:
and / or
2024
Journal article
Open Access
Fulgor: a fast and compact k-mer index for large-scale matching and color queries
Fan J., Khan J., Pratap Singh N., Pibiri G. E., Patro R.
The problem of sequence identification or matching--determining the subset of reference sequences from a given collection that are likely to contain a short, queried nucleotide sequence--is relevant for many important tasks in Computational Biology, such as metagenomics and pangenome analysis. Due to the complex nature of such analyses and the large scale of the reference collections a resource-efficient solution to this problem is of utmost importance. This poses the threefold challenge of representing the reference collection with a data structure that is efficient to query, has light memory usage, and scales well to large collections. To solve this problem, we describe an efficient colored de Bruijn graph index, arising as the combination of a k-mer dictionary with a compressed inverted index. The proposed index takes full advantage of the fact that unitigs in the colored compacted de Bruijn graph are monochromatic (i.e., all k-mers in a unitig have the same set of references of origin, or color). Specifically, the unitigs are kept in the dictionary in color order, thereby allowing for the encoding of the map from k-mers to their colors in as little as 1 + o(1) bits per unitig. Hence, one color per unitig is stored in the index with almost no space/time overhead. By combining this property with simple but effective compression methods for integer lists, the index achieves very small space. We implement these methods in a tool called Fulgor, and conduct an extensive experimental analysis to demonstrate the improvement of our tool over previous solutions. For example, compared to Themisto--the strongest competitor in terms of index space vs. query time trade-off--Fulgor requires significantly less space (up to 43% less space for a collection of 150,000 Salmonella enterica genomes), is at least twice as fast for color queries, and is 2-6× faster to construct.Source: Algorithms for molecular biology 19 (2024). doi:10.1186/s13015-024-00251-9
DOI: 10.1186/s13015-024-00251-9
Metrics:
Fan J., Khan J., Pratap Singh N., Pibiri G. E., Patro R.
The problem of sequence identification or matching--determining the subset of reference sequences from a given collection that are likely to contain a short, queried nucleotide sequence--is relevant for many important tasks in Computational Biology, such as metagenomics and pangenome analysis. Due to the complex nature of such analyses and the large scale of the reference collections a resource-efficient solution to this problem is of utmost importance. This poses the threefold challenge of representing the reference collection with a data structure that is efficient to query, has light memory usage, and scales well to large collections. To solve this problem, we describe an efficient colored de Bruijn graph index, arising as the combination of a k-mer dictionary with a compressed inverted index. The proposed index takes full advantage of the fact that unitigs in the colored compacted de Bruijn graph are monochromatic (i.e., all k-mers in a unitig have the same set of references of origin, or color). Specifically, the unitigs are kept in the dictionary in color order, thereby allowing for the encoding of the map from k-mers to their colors in as little as 1 + o(1) bits per unitig. Hence, one color per unitig is stored in the index with almost no space/time overhead. By combining this property with simple but effective compression methods for integer lists, the index achieves very small space. We implement these methods in a tool called Fulgor, and conduct an extensive experimental analysis to demonstrate the improvement of our tool over previous solutions. For example, compared to Themisto--the strongest competitor in terms of index space vs. query time trade-off--Fulgor requires significantly less space (up to 43% less space for a collection of 150,000 Salmonella enterica genomes), is at least twice as fast for color queries, and is 2-6× faster to construct.Source: Algorithms for molecular biology 19 (2024). doi:10.1186/s13015-024-00251-9
DOI: 10.1186/s13015-024-00251-9
Metrics:
See at:
almob.biomedcentral.com 
| ISTI Repository | CNR ExploRA
2023
Conference article
Open Access
Spectrum preserving tilings enable sparse and modular reference indexing
Fan J., Khan J., Pibiri G. E., Patro R.
The reference indexing problem for -mers is to pre-process a collection of reference genomic sequences so that the position of all occurrences of any queried -mer can be rapidly identified. An efficient and scalable solution to this problem is fundamental for many tasks in bioinformatics. In this work, we introduce the spectrum preserving tiling (SPT), a general representation of that specifies how a set of tiles repeatedly occur to spell out the constituent reference sequences in. By encoding the order and positions where tiles occur, SPTs enable the implementation and analysis of a general class of modular indexes. An index over an SPT decomposes the reference indexing problem for -mers into: (1) a -mer-to-tile mapping; and (2) a tile-to-occurrence mapping. Recently introduced work to construct and compactly index -mer sets can be used to efficiently implement the -mer-to-tile mapping. However, implementing the tile-to-occurrence mapping remains prohibitively costly in terms of space. As reference collections become large, the space requirements of the tile-to-occurrence mapping dominates that of the -mer-to-tile mapping since the former depends on the amount of total sequence while the latter depends on the number of unique -mers in. To address this, we introduce a class of sampling schemes for SPTs that trade off speed to reduce the size of the tile-to-reference mapping. We implement a practical index with these sampling schemes in the tool pufferfish2. When indexing over 30,000 bacterial genomes, pufferfish2 reduces the size of the tile-to-occurrence mapping from 86.3 GB to 34.6 GB while incurring only a 3.6 slowdown when querying -mers from a sequenced readset. Availability: pufferfish2 is implemented in Rust and available at https://github.com/COMBINE-lab/pufferfish2.Source: RECOMB 2023 - 27th International Conference on Research in Computational Molecular Biology, pp. 21–40, Istanbul, Turkey, 16-19/04/2023
DOI: 10.1007/978-3-031-29119-7_2
Project(s): MobiDataLab
Metrics:
Fan J., Khan J., Pibiri G. E., Patro R.
The reference indexing problem for -mers is to pre-process a collection of reference genomic sequences so that the position of all occurrences of any queried -mer can be rapidly identified. An efficient and scalable solution to this problem is fundamental for many tasks in bioinformatics. In this work, we introduce the spectrum preserving tiling (SPT), a general representation of that specifies how a set of tiles repeatedly occur to spell out the constituent reference sequences in. By encoding the order and positions where tiles occur, SPTs enable the implementation and analysis of a general class of modular indexes. An index over an SPT decomposes the reference indexing problem for -mers into: (1) a -mer-to-tile mapping; and (2) a tile-to-occurrence mapping. Recently introduced work to construct and compactly index -mer sets can be used to efficiently implement the -mer-to-tile mapping. However, implementing the tile-to-occurrence mapping remains prohibitively costly in terms of space. As reference collections become large, the space requirements of the tile-to-occurrence mapping dominates that of the -mer-to-tile mapping since the former depends on the amount of total sequence while the latter depends on the number of unique -mers in. To address this, we introduce a class of sampling schemes for SPTs that trade off speed to reduce the size of the tile-to-reference mapping. We implement a practical index with these sampling schemes in the tool pufferfish2. When indexing over 30,000 bacterial genomes, pufferfish2 reduces the size of the tile-to-occurrence mapping from 86.3 GB to 34.6 GB while incurring only a 3.6 slowdown when querying -mers from a sequenced readset. Availability: pufferfish2 is implemented in Rust and available at https://github.com/COMBINE-lab/pufferfish2.Source: RECOMB 2023 - 27th International Conference on Research in Computational Molecular Biology, pp. 21–40, Istanbul, Turkey, 16-19/04/2023
DOI: 10.1007/978-3-031-29119-7_2
Project(s): MobiDataLab
Metrics:
See at:
link.springer.com | ISTI Repository | CNR ExploRA
2023
Journal article
Open Access
On weighted k-mer dictionaries
Pibiri G. E.
We consider the problem of representing a set of k-mers and their abundance counts, or weights, in compressed space so that assessing membership and retrieving the weight of a k-mer is efficient. The representation is called a weighted dictionary of k-mers and finds application in numerous tasks in Bioinformatics that usually count k-mers as a pre-processing step. In fact, k-mer counting tools produce very large outputs that may result in a severe bottleneck for subsequent processing. In this work we extend the recently introduced SSHash dictionary (Pibiri in Bioinformatics 38:185-194, 2022) to also store compactly the weights of the k-mers. From a technical perspective, we exploit the order of the k-mers represented in SSHash to encode runs of weights, hence allowing much better compression than the empirical entropy of the weights. We study the problem of reducing the number of runs in the weights to improve compression even further and give an optimal algorithm for this problem. Lastly, we corroborate our findings with experiments on real-world datasets and comparison with competitive alternatives. Up to date, SSHash is the only k-mer dictionary that is exact, weighted, associative, fast, and small.Source: Algorithms for molecular biology 18 (2023). doi:10.1186/s13015-023-00226-2
DOI: 10.1186/s13015-023-00226-2
Metrics:
Pibiri G. E.
We consider the problem of representing a set of k-mers and their abundance counts, or weights, in compressed space so that assessing membership and retrieving the weight of a k-mer is efficient. The representation is called a weighted dictionary of k-mers and finds application in numerous tasks in Bioinformatics that usually count k-mers as a pre-processing step. In fact, k-mer counting tools produce very large outputs that may result in a severe bottleneck for subsequent processing. In this work we extend the recently introduced SSHash dictionary (Pibiri in Bioinformatics 38:185-194, 2022) to also store compactly the weights of the k-mers. From a technical perspective, we exploit the order of the k-mers represented in SSHash to encode runs of weights, hence allowing much better compression than the empirical entropy of the weights. We study the problem of reducing the number of runs in the weights to improve compression even further and give an optimal algorithm for this problem. Lastly, we corroborate our findings with experiments on real-world datasets and comparison with competitive alternatives. Up to date, SSHash is the only k-mer dictionary that is exact, weighted, associative, fast, and small.Source: Algorithms for molecular biology 18 (2023). doi:10.1186/s13015-023-00226-2
DOI: 10.1186/s13015-023-00226-2
Metrics:
See at:
almob.biomedcentral.com | ISTI Repository | CNR ExploRA
2023
Journal article
Open Access
Matchtigs: minimum plain text representation of k-mer sets
Schmidt S., Khan S., Alanko J. N., Pibiri G. E., Tomescu A. I.
We propose a polynomial algorithm computing a minimum plain-text representation of k-mer sets, as well as an efficient near-minimum greedy heuristic. When compressing read sets of large model organisms or bacterial pangenomes, with only a minor runtime increase, we shrink the representation by up to 59% over unitigs and 26% over previous work. Additionally, the number of strings is decreased by up to 97% over unitigs and 90% over previous work. Finally, a small representation has advantages in downstream applications, as it speeds up SSHash-Lite queries by up to 4.26× over unitigs and 2.10× over previous work.Source: Genome biology (Online) 24 (2023). doi:10.1186/s13059-023-02968-z
DOI: 10.1186/s13059-023-02968-z
Project(s): MobiDataLab, SAFEBIO
Metrics:
Schmidt S., Khan S., Alanko J. N., Pibiri G. E., Tomescu A. I.
We propose a polynomial algorithm computing a minimum plain-text representation of k-mer sets, as well as an efficient near-minimum greedy heuristic. When compressing read sets of large model organisms or bacterial pangenomes, with only a minor runtime increase, we shrink the representation by up to 59% over unitigs and 26% over previous work. Additionally, the number of strings is decreased by up to 97% over unitigs and 90% over previous work. Finally, a small representation has advantages in downstream applications, as it speeds up SSHash-Lite queries by up to 4.26× over unitigs and 2.10× over previous work.Source: Genome biology (Online) 24 (2023). doi:10.1186/s13059-023-02968-z
DOI: 10.1186/s13059-023-02968-z
Project(s): MobiDataLab
, SAFEBIO Metrics:
See at:
genomebiology.biomedcentral.com | ISTI Repository | CNR ExploRA
2023
Journal article
Open Access
Locality-preserving minimal perfect hashing of k-mers
Pibiri G. E., Shibuya Y., Limasset A.
Motivation: Minimal perfect hashing is the problem of mapping a static set of n distinct keys into the address space {1, ... , n} bijectively. It is well-known that n log2(e) bits are necessary to specify a minimal perfect hash function (MPHF) f, when no additional knowledge of the input keys is to be used. However, it is often the case in practice that the input keys have intrinsic relationships that we can exploit to lower the bit complexity of f. For example, consider a string and the set of all its distinct k-mers as input keys: since two consecutive k-mers share an overlap of k - 1 symbols, it seems possible to beat the classic log2(e) bits/key barrier in this case. Moreover, we would like f to map consecutive k-mers to consecutive addresses, as to also preserve as much as possible their relationship in the codomain. This is a useful feature in practice as it guarantees a certain degree of locality of reference for f, resulting in a better evaluation time when querying consecutive k-mers.Results: Motivated by these premises, we initiate the study of a new type of locality-preserving MPHF designed for k-mers extracted consecutively from a collection of strings. We design a construction whose space usage decreases for growing k and discuss experiments with a practical implementation of the method: in practice, the functions built with our method can be several times smaller and even faster to query than the most efficient MPHFs in the literature.Code Availability: https://github.com/jermp/lphashData Availability: https://zenodo.org/record/7239205Source: Bioinformatics (Oxf., Online) 39 (2023): i534–i543. doi:10.1093/bioinformatics/btad219
DOI: 10.1093/bioinformatics/btad219
Metrics:
Pibiri G. E., Shibuya Y., Limasset A.
Motivation: Minimal perfect hashing is the problem of mapping a static set of n distinct keys into the address space {1, ... , n} bijectively. It is well-known that n log2(e) bits are necessary to specify a minimal perfect hash function (MPHF) f, when no additional knowledge of the input keys is to be used. However, it is often the case in practice that the input keys have intrinsic relationships that we can exploit to lower the bit complexity of f. For example, consider a string and the set of all its distinct k-mers as input keys: since two consecutive k-mers share an overlap of k - 1 symbols, it seems possible to beat the classic log2(e) bits/key barrier in this case. Moreover, we would like f to map consecutive k-mers to consecutive addresses, as to also preserve as much as possible their relationship in the codomain. This is a useful feature in practice as it guarantees a certain degree of locality of reference for f, resulting in a better evaluation time when querying consecutive k-mers.Results: Motivated by these premises, we initiate the study of a new type of locality-preserving MPHF designed for k-mers extracted consecutively from a collection of strings. We design a construction whose space usage decreases for growing k and discuss experiments with a practical implementation of the method: in practice, the functions built with our method can be several times smaller and even faster to query than the most efficient MPHFs in the literature.Code Availability: https://github.com/jermp/lphashData Availability: https://zenodo.org/record/7239205Source: Bioinformatics (Oxf., Online) 39 (2023): i534–i543. doi:10.1093/bioinformatics/btad219
DOI: 10.1093/bioinformatics/btad219
Metrics:
See at:
academic.oup.com | ISTI Repository | ISTI Repository | CNR ExploRA
2023
Journal article
Open Access
Parallel and external-memory construction of minimal perfect hash functions with PTHash
Pibiri G. E., Trani R.
A function is a minimal perfect hash function for a set of size , if bijectively maps into the first n natural numbers. These functions are important for many practical applications in computing, such as search engines, computer networks, and databases. Several algorithms have been proposed to build minimal perfect hash functions that: scale well to large sets, retain fast evaluation time, and take very little space, e.g., 2 - 3 bits/key. PTHash is one such algorithm, achieving very fast evaluation in compressed space, typically many times faster than other techniques. In this work, we propose a new construction algorithm for PTHash enabling: (1) , to either build functions more quickly or more space-efficiently, and (2) , to scale to inputs much larger than the available internal memory. Only few other algorithms in the literature share these features, despite of their practical impact. We conduct an extensive experimental assessment on large real-world string collections and show that, with respect to other techniques, PTHash is competitive in construction time and space consumption, but retains 2 - 6× better lookup time.Source: IEEE transactions on knowledge and data engineering (Online) (2023). doi:10.1109/TKDE.2023.3303341
DOI: 10.1109/tkde.2023.3303341
Metrics:
Pibiri G. E., Trani R.
A function is a minimal perfect hash function for a set of size , if bijectively maps into the first n natural numbers. These functions are important for many practical applications in computing, such as search engines, computer networks, and databases. Several algorithms have been proposed to build minimal perfect hash functions that: scale well to large sets, retain fast evaluation time, and take very little space, e.g., 2 - 3 bits/key. PTHash is one such algorithm, achieving very fast evaluation in compressed space, typically many times faster than other techniques. In this work, we propose a new construction algorithm for PTHash enabling: (1) , to either build functions more quickly or more space-efficiently, and (2) , to scale to inputs much larger than the available internal memory. Only few other algorithms in the literature share these features, despite of their practical impact. We conduct an extensive experimental assessment on large real-world string collections and show that, with respect to other techniques, PTHash is competitive in construction time and space consumption, but retains 2 - 6× better lookup time.Source: IEEE transactions on knowledge and data engineering (Online) (2023). doi:10.1109/TKDE.2023.3303341
DOI: 10.1109/tkde.2023.3303341
Metrics:
See at:
ISTI Repository | ieeexplore.ieee.org 
| CNR ExploRA
2023
Conference article
Open Access
Fulgor: a fast and compact {k-mer} index for large-scale matching and color queries
Fan J., Singh N. P., Khan J., Pibiri G. E., Patro R.
The problem of sequence identification or matching - determining the subset of reference sequences from a given collection that are likely to contain a short, queried nucleotide sequence - is relevant for many important tasks in Computational Biology, such as metagenomics and pan-genome analysis. Due to the complex nature of such analyses and the large scale of the reference collections a resource-efficient solution to this problem is of utmost importance. This poses the threefold challenge of representing the reference collection with a data structure that is efficient to query, has light memory usage, and scales well to large collections. To solve this problem, we describe how recent advancements in associative, order-preserving, k-mer dictionaries can be combined with a compressed inverted index to implement a fast and compact colored de Bruijn graph data structure. This index takes full advantage of the fact that unitigs in the colored de Bruijn graph are monochromatic (all k-mers in a unitig have the same set of references of origin, or "color"), leveraging the order-preserving property of its dictionary. In fact, k-mers are kept in unitig order by the dictionary, thereby allowing for the encoding of the map from k-mers to their inverted lists in as little as 1+o(1) bits per unitig. Hence, one inverted list per unitig is stored in the index with almost no space/time overhead. By combining this property with simple but effective compression methods for inverted lists, the index achieves very small space. We implement these methods in a tool called Fulgor. Compared to Themisto, the prior state of the art, Fulgor indexes a heterogeneous collection of 30,691 bacterial genomes in 3.8× less space, a collection of 150,000 Salmonella enterica genomes in approximately 2× less space, is at least twice as fast for color queries, and is 2-6 × faster to construct.Source: WABI 223 - 23rd International Workshop on Algorithms in Bioinformatics, pp. 18:1–18:21, Houston, Texas (USA), 03-06/09/2023
DOI: 10.4230/lipics.wabi.2023.18
DOI: 10.1101/2023.05.09.539895
Metrics:
Fan J., Singh N. P., Khan J., Pibiri G. E., Patro R.
The problem of sequence identification or matching - determining the subset of reference sequences from a given collection that are likely to contain a short, queried nucleotide sequence - is relevant for many important tasks in Computational Biology, such as metagenomics and pan-genome analysis. Due to the complex nature of such analyses and the large scale of the reference collections a resource-efficient solution to this problem is of utmost importance. This poses the threefold challenge of representing the reference collection with a data structure that is efficient to query, has light memory usage, and scales well to large collections. To solve this problem, we describe how recent advancements in associative, order-preserving, k-mer dictionaries can be combined with a compressed inverted index to implement a fast and compact colored de Bruijn graph data structure. This index takes full advantage of the fact that unitigs in the colored de Bruijn graph are monochromatic (all k-mers in a unitig have the same set of references of origin, or "color"), leveraging the order-preserving property of its dictionary. In fact, k-mers are kept in unitig order by the dictionary, thereby allowing for the encoding of the map from k-mers to their inverted lists in as little as 1+o(1) bits per unitig. Hence, one inverted list per unitig is stored in the index with almost no space/time overhead. By combining this property with simple but effective compression methods for inverted lists, the index achieves very small space. We implement these methods in a tool called Fulgor. Compared to Themisto, the prior state of the art, Fulgor indexes a heterogeneous collection of 30,691 bacterial genomes in 3.8× less space, a collection of 150,000 Salmonella enterica genomes in approximately 2× less space, is at least twice as fast for color queries, and is 2-6 × faster to construct.Source: WABI 223 - 23rd International Workshop on Algorithms in Bioinformatics, pp. 18:1–18:21, Houston, Texas (USA), 03-06/09/2023
DOI: 10.4230/lipics.wabi.2023.18
DOI: 10.1101/2023.05.09.539895
Metrics:
See at:
drops.dagstuhl.de | Europe PubMed Central | Archivio istituzionale della ricerca - Università degli Studi di Venezia Ca' Foscari | doi.org | doi.org | pubmed.ncbi.nlm.nih.gov | CNR ExploRA
2022
Journal article
Open Access
Sparse and skew hashing of K-mers
Pibiri G. E.
MOTIVATION: A dictionary of k-mers is a data structure that stores a set of n distinct k-mers and supports membership queries. This data structure is at the hearth of many important tasks in computational biology. High-throughput sequencing of DNA can produce very large k-mer sets, in the size of billions of strings-in such cases, the memory consumption and query efficiency of the data structure is a concrete challenge. RESULTS: To tackle this problem, we describe a compressed and associative dictionary for k-mers, that is: a data structure where strings are represented in compact form and each of them is associated to a unique integer identifier in the range [0,n). We show that some statistical properties of k-mer minimizers can be exploited by minimal perfect hashing to substantially improve the space/time trade-off of the dictionary compared to the best-known solutions. AVAILABILITY AND IMPLEMENTATION: https://github.com/jermp/sshash. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.Source: Bioinformatics (Oxf., Online) 38 (2022): i185–i194. doi:10.1093/bioinformatics/btac245
DOI: 10.1093/bioinformatics/btac245
Project(s): MobiDataLab
Metrics:
Pibiri G. E.
MOTIVATION: A dictionary of k-mers is a data structure that stores a set of n distinct k-mers and supports membership queries. This data structure is at the hearth of many important tasks in computational biology. High-throughput sequencing of DNA can produce very large k-mer sets, in the size of billions of strings-in such cases, the memory consumption and query efficiency of the data structure is a concrete challenge. RESULTS: To tackle this problem, we describe a compressed and associative dictionary for k-mers, that is: a data structure where strings are represented in compact form and each of them is associated to a unique integer identifier in the range [0,n). We show that some statistical properties of k-mer minimizers can be exploited by minimal perfect hashing to substantially improve the space/time trade-off of the dictionary compared to the best-known solutions. AVAILABILITY AND IMPLEMENTATION: https://github.com/jermp/sshash. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.Source: Bioinformatics (Oxf., Online) 38 (2022): i185–i194. doi:10.1093/bioinformatics/btac245
DOI: 10.1093/bioinformatics/btac245
Project(s): MobiDataLab
Metrics:
See at:
academic.oup.com | ISTI Repository | CNR ExploRA
2022
Conference article
Open Access
On weighted k-mer dictionaries
Pibiri G. E.
We consider the problem of representing a set of k-mers and their abundance counts, or weights, in compressed space so that assessing membership and retrieving the weight of a k-mer is efficient. The representation is called a weighted dictionary of k-mers and finds application in numerous tasks in Bioinformatics that usually count k-mers as a pre-processing step. In fact, k-mer counting tools produce very large outputs that may result in a severe bottleneck for subsequent processing. In this work we extend the recently introduced SSHash dictionary (Pibiri, Bioinformatics 2022) to also store compactly the weights of the k-mers. From a technical perspective, we exploit the order of the k-mers represented in SSHash to encode runs of weights, hence allowing (several times) better compression than the empirical entropy of the weights. We also study the problem of reducing the number of runs in the weights to improve compression even further and illustrate a lower bound for this problem. We propose an efficient, greedy, algorithm to reduce the number of runs and show empirically that it performs well, i.e., very similarly to the lower bound. Lastly, we corroborate our findings with experiments on real-world datasets and comparison with competitive alternatives. Up to date, SSHash is the only k-mer dictionary that is exact, weighted, associative, fast, and small.Source: WABI 2022 - International Workshop on Algorithms in Bioinformatics, Potsdam, Germany, 05-09/09/2022
DOI: 10.4230/lipics.wabi.2022.9
Project(s): MobiDataLab
Metrics:
Pibiri G. E.
We consider the problem of representing a set of k-mers and their abundance counts, or weights, in compressed space so that assessing membership and retrieving the weight of a k-mer is efficient. The representation is called a weighted dictionary of k-mers and finds application in numerous tasks in Bioinformatics that usually count k-mers as a pre-processing step. In fact, k-mer counting tools produce very large outputs that may result in a severe bottleneck for subsequent processing. In this work we extend the recently introduced SSHash dictionary (Pibiri, Bioinformatics 2022) to also store compactly the weights of the k-mers. From a technical perspective, we exploit the order of the k-mers represented in SSHash to encode runs of weights, hence allowing (several times) better compression than the empirical entropy of the weights. We also study the problem of reducing the number of runs in the weights to improve compression even further and illustrate a lower bound for this problem. We propose an efficient, greedy, algorithm to reduce the number of runs and show empirically that it performs well, i.e., very similarly to the lower bound. Lastly, we corroborate our findings with experiments on real-world datasets and comparison with competitive alternatives. Up to date, SSHash is the only k-mer dictionary that is exact, weighted, associative, fast, and small.Source: WABI 2022 - International Workshop on Algorithms in Bioinformatics, Potsdam, Germany, 05-09/09/2022
DOI: 10.4230/lipics.wabi.2022.9
Project(s): MobiDataLab
Metrics:
See at:
drops.dagstuhl.de | ISTI Repository | CNR ExploRA
2021
Conference article
Open Access
Fast and compact set intersection through recursive universe partitioning
Pibiri G. E.
We present a data structure that encodes a sorted integer sequence in small space allowing, at the same time, fast intersection operations. The data layout is carefully designed to exploit word-level parallelism and SIMD instructions, hence providing good practical performance. The core algorithmic idea is that of recursive partitioning the universe of representation: a markedly different paradigm than the widespread strategy of partitioning the sequence based on its length. Extensive experimentation and comparison against several competitive techniques shows that the proposed solution embodies an improved space/time trade-off for the set intersection problem.Source: DCC 2021 - IEEE Data Compression Conference, pp. 293–302, Online Conference, 23-26/03/2021
DOI: 10.1109/dcc50243.2021.00037
Metrics:
Pibiri G. E.
We present a data structure that encodes a sorted integer sequence in small space allowing, at the same time, fast intersection operations. The data layout is carefully designed to exploit word-level parallelism and SIMD instructions, hence providing good practical performance. The core algorithmic idea is that of recursive partitioning the universe of representation: a markedly different paradigm than the widespread strategy of partitioning the sequence based on its length. Extensive experimentation and comparison against several competitive techniques shows that the proposed solution embodies an improved space/time trade-off for the set intersection problem.Source: DCC 2021 - IEEE Data Compression Conference, pp. 293–302, Online Conference, 23-26/03/2021
DOI: 10.1109/dcc50243.2021.00037
Metrics:
See at:
ISTI Repository | doi.org | ieeexplore.ieee.org | CNR ExploRA
2021
Journal article
Open Access
Rank/select queries over mutable bitmaps
Pibiri G. E., Kanda S.
The problem of answering rank/select queries over a bitmap is of utmost importance for many succinct data structures. When the bitmap does not change, many solutions exist in the theoretical and practical side. In this work we consider the case where one is allowed to modify the bitmap via a flip(i) operation that toggles its i-th bit. By adapting and properly extending some results concerning prefix-sum data structures, we present a practical solution to the problem, tailored for modern CPU instruction sets. Compared to the state-of-the-art, our solution improves runtime with no space degradation. Moreover, it does not incur in a significant runtime penalty when compared to the fastest immutable indexes, while providing even lower space overhead.Source: Information systems (Oxf.) 99 (2021). doi:10.1016/j.is.2021.101756
DOI: 10.1016/j.is.2021.101756
DOI: 10.48550/arxiv.2009.12809
Project(s): BigDataGrapes
Metrics:
Pibiri G. E., Kanda S.
The problem of answering rank/select queries over a bitmap is of utmost importance for many succinct data structures. When the bitmap does not change, many solutions exist in the theoretical and practical side. In this work we consider the case where one is allowed to modify the bitmap via a flip(i) operation that toggles its i-th bit. By adapting and properly extending some results concerning prefix-sum data structures, we present a practical solution to the problem, tailored for modern CPU instruction sets. Compared to the state-of-the-art, our solution improves runtime with no space degradation. Moreover, it does not incur in a significant runtime penalty when compared to the fastest immutable indexes, while providing even lower space overhead.Source: Information systems (Oxf.) 99 (2021). doi:10.1016/j.is.2021.101756
DOI: 10.1016/j.is.2021.101756
DOI: 10.48550/arxiv.2009.12809
Project(s): BigDataGrapes
Metrics:
See at:
arXiv.org e-Print Archive | Information Systems | ISTI Repository | Information Systems | doi.org | www.sciencedirect.com | CNR ExploRA
2021
Contribution to conference
Open Access
Compressed indexes for fast search of semantic data
Perego R., Pibiri G. E., Venturini R.
The sheer increase in volume of RDF data demands efficient solutions for the triple indexing problem, that is devising a compressed data structure to compactly represent RDF triples by guaranteeing, at the same time, fast pattern matching operations. This problem lies at the heart of delivering good practical performance for the resolution of complex SPARQL queries on large RDF datasets. We propose a trie-based index layout to solve the problem and introduce two novel techniques to reduce its space of representation for improved effectiveness. The extensive experimental analysis reveals that our best space/time trade-off configuration substantially outperforms existing solutions at the state-of-the-art, by taking 30-60% less space and speeding up query execution by a factor of 2-81 times.Source: ICDE 2021 - 37th IEEE International Conference on Data Engineering, pp. 2325–2326, Online conference, 19-22/04/2021
DOI: 10.1109/icde51399.2021.00248
Project(s): BigDataGrapes
Metrics:
Perego R., Pibiri G. E., Venturini R.
The sheer increase in volume of RDF data demands efficient solutions for the triple indexing problem, that is devising a compressed data structure to compactly represent RDF triples by guaranteeing, at the same time, fast pattern matching operations. This problem lies at the heart of delivering good practical performance for the resolution of complex SPARQL queries on large RDF datasets. We propose a trie-based index layout to solve the problem and introduce two novel techniques to reduce its space of representation for improved effectiveness. The extensive experimental analysis reveals that our best space/time trade-off configuration substantially outperforms existing solutions at the state-of-the-art, by taking 30-60% less space and speeding up query execution by a factor of 2-81 times.Source: ICDE 2021 - 37th IEEE International Conference on Data Engineering, pp. 2325–2326, Online conference, 19-22/04/2021
DOI: 10.1109/icde51399.2021.00248
Project(s): BigDataGrapes
Metrics:
See at:
ISTI Repository | ieeexplore.ieee.org | CNR ExploRA
2021
Conference article
Open Access
PTHash: revisiting FCH minimal perfect hashing
Pibiri G. M., Trani R.
Given a set S of n distinct keys, a function f that bijectively maps the keys of S into the range {0,...,n-1} is called a minimal perfect hash function for S. Algorithms that find such functions when n is large and retain constant evaluation time are of practical interest; for instance, search engines and databases typically use minimal perfect hash functions to quickly assign identifiers to static sets of variable-length keys such as strings. The challenge is to design an algorithm which is efficient in three different aspects: time to find f (construction time), time to evaluate f on a key of S (lookup time), and space of representation for f . Several algorithms have been proposed to trade-off between these aspects. In 1992, Fox, Chen, and Heath (FCH) presented an algorithm at SIGIR providing very fast lookup evaluation. However, the approach received little attention because of its large construction time and higher space consumption compared to other subsequent techniques. Almost thirty years later we revisit their framework and present an improved algorithm that scales well to large sets and reduces space consumption altogether, without compromising the lookup time. We conduct an extensive experimental assessment and show that the algorithm finds functions that are competitive in space with state-of-the art techniques and provide 2 - 4X better lookup time.Source: SIGIR '21 - 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 1339–1348, Canada, Montreal (Virtual Event), 11-15/07/2021
DOI: 10.1145/3404835.3462849
Metrics:
Pibiri G. M., Trani R.
Given a set S of n distinct keys, a function f that bijectively maps the keys of S into the range {0,...,n-1} is called a minimal perfect hash function for S. Algorithms that find such functions when n is large and retain constant evaluation time are of practical interest; for instance, search engines and databases typically use minimal perfect hash functions to quickly assign identifiers to static sets of variable-length keys such as strings. The challenge is to design an algorithm which is efficient in three different aspects: time to find f (construction time), time to evaluate f on a key of S (lookup time), and space of representation for f . Several algorithms have been proposed to trade-off between these aspects. In 1992, Fox, Chen, and Heath (FCH) presented an algorithm at SIGIR providing very fast lookup evaluation. However, the approach received little attention because of its large construction time and higher space consumption compared to other subsequent techniques. Almost thirty years later we revisit their framework and present an improved algorithm that scales well to large sets and reduces space consumption altogether, without compromising the lookup time. We conduct an extensive experimental assessment and show that the algorithm finds functions that are competitive in space with state-of-the art techniques and provide 2 - 4X better lookup time.Source: SIGIR '21 - 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 1339–1348, Canada, Montreal (Virtual Event), 11-15/07/2021
DOI: 10.1145/3404835.3462849
Metrics:
See at:
ISTI Repository | dl.acm.org | CNR ExploRA
2021
Conference article
Open Access
TSXor: a simple time series compression algorithm
Bruno A., Nardini F. M., Pibiri G. E., Trani R., Venturini R.
Time series are ubiquitous in computing as a key ingredient of many machine learning analytics, ranging from classification to forecasting. Typically, the training of such machine learning algorithms on time series requires to access the data in temporal order for several times. Therefore, a compression algorithm providing good compression ratios and fast decompression speed is desirable. In this paper, we present TSXor, a simple yet effective lossless compressor for time series. The main idea is to exploit the redundancy/similarity between close-in-time values through a window that acts as a cache, as to improve the compression ratio and decompression speed. We show that TSXor achieves up to 3× better compression and up to 2× faster decompression than the state of the art on real-world datasets.Source: SPIRE 2021 - International Symposium on String Processing and Information Retrieval, pp. 217–223, France, Lille (Virtual Event), 04/10/2021-06/10/2021
DOI: 10.1007/978-3-030-86692-1_18
Metrics:
Bruno A., Nardini F. M., Pibiri G. E., Trani R., Venturini R.
Time series are ubiquitous in computing as a key ingredient of many machine learning analytics, ranging from classification to forecasting. Typically, the training of such machine learning algorithms on time series requires to access the data in temporal order for several times. Therefore, a compression algorithm providing good compression ratios and fast decompression speed is desirable. In this paper, we present TSXor, a simple yet effective lossless compressor for time series. The main idea is to exploit the redundancy/similarity between close-in-time values through a window that acts as a cache, as to improve the compression ratio and decompression speed. We show that TSXor achieves up to 3× better compression and up to 2× faster decompression than the state of the art on real-world datasets.Source: SPIRE 2021 - International Symposium on String Processing and Information Retrieval, pp. 217–223, France, Lille (Virtual Event), 04/10/2021-06/10/2021
DOI: 10.1007/978-3-030-86692-1_18
Metrics:
See at:
ISTI Repository | link.springer.com | CNR ExploRA
2020
Journal article
Open Access
Compressed indexes for fast search of semantic data
Pibiri G. E., Perego R., Venturini R.
The sheer increase in volume of RDF data demands efficient solutions for the triple indexing problem, that is to devise a compressed data structure to compactly represent RDF triples by guaranteeing, at the same time, fast pattern matching operations. This problem lies at the heart of delivering good practical performance for the resolution of complex SPARQL queries on large RDF datasets. In this work, we propose a trie-based index layout to solve the problem and introduce two novel techniques to reduce its space of representation for improved effectiveness. The extensive experimental analysis, conducted over a wide range of publicly available real-world datasets, reveals that our best space/time trade-off configuration substantially outperforms existing solutions at the state-of-the-art, by taking 30 - 60% less space and speeding up query execution by a factor of 2-81× .Source: IEEE transactions on knowledge and data engineering (Print) 33 (2020): 3187–3198. doi:10.1109/TKDE.2020.2966609
DOI: 10.1109/tkde.2020.2966609
DOI: 10.48550/arxiv.1904.07619
Project(s): BigDataGrapes
Metrics:
Pibiri G. E., Perego R., Venturini R.
The sheer increase in volume of RDF data demands efficient solutions for the triple indexing problem, that is to devise a compressed data structure to compactly represent RDF triples by guaranteeing, at the same time, fast pattern matching operations. This problem lies at the heart of delivering good practical performance for the resolution of complex SPARQL queries on large RDF datasets. In this work, we propose a trie-based index layout to solve the problem and introduce two novel techniques to reduce its space of representation for improved effectiveness. The extensive experimental analysis, conducted over a wide range of publicly available real-world datasets, reveals that our best space/time trade-off configuration substantially outperforms existing solutions at the state-of-the-art, by taking 30 - 60% less space and speeding up query execution by a factor of 2-81× .Source: IEEE transactions on knowledge and data engineering (Print) 33 (2020): 3187–3198. doi:10.1109/TKDE.2020.2966609
DOI: 10.1109/tkde.2020.2966609
DOI: 10.48550/arxiv.1904.07619
Project(s): BigDataGrapes
Metrics:
See at:
arXiv.org e-Print Archive | IEEE Transactions on Knowledge and Data Engineering | ISTI Repository | IEEE Transactions on Knowledge and Data Engineering | doi.org | ieeexplore.ieee.org | CNR ExploRA
2020
Conference article
Open Access
Efficient and effective query auto-completion
Gog S., Pibiri G. E., Venturini R.
Query Auto-Completion (QAC) is an ubiquitous feature of modern textual search systems, suggesting possible ways of completing the query being typed by the user. Efficiency is crucial to make the system have a real-time responsiveness when operating in the million-scale search space. Prior work has extensively advocated the use of a trie data structure for fast prefix-search operations in compact space. However, searching by prefix has little discovery power in that only completions that are prefixed by the query are returned. This may impact negatively the effectiveness of the QAC system, with a consequent monetary loss for real applications like Web Search Engines and eCommerce. In this work we describe the implementation that empowers a new QAC system at eBay, and discuss its efficiency/effectiveness in relation to other approaches at the state-of-the-art. The solution is based on the combination of an inverted index with succinct data structures, a much less explored direction in the literature. This system is replacing the previous implementation based on Apache SOLR that was not always able to meet the required service-level-agreement.Source: ACM Conference on Research and Development in Information Retrieval, pp. 2271–2280, 25/07/2020-30/07/2020
DOI: 10.1145/3397271.3401432
DOI: 10.48550/arxiv.2005.06213
Project(s): BigDataGrapes
Metrics:
Gog S., Pibiri G. E., Venturini R.
Query Auto-Completion (QAC) is an ubiquitous feature of modern textual search systems, suggesting possible ways of completing the query being typed by the user. Efficiency is crucial to make the system have a real-time responsiveness when operating in the million-scale search space. Prior work has extensively advocated the use of a trie data structure for fast prefix-search operations in compact space. However, searching by prefix has little discovery power in that only completions that are prefixed by the query are returned. This may impact negatively the effectiveness of the QAC system, with a consequent monetary loss for real applications like Web Search Engines and eCommerce. In this work we describe the implementation that empowers a new QAC system at eBay, and discuss its efficiency/effectiveness in relation to other approaches at the state-of-the-art. The solution is based on the combination of an inverted index with succinct data structures, a much less explored direction in the literature. This system is replacing the previous implementation based on Apache SOLR that was not always able to meet the required service-level-agreement.Source: ACM Conference on Research and Development in Information Retrieval, pp. 2271–2280, 25/07/2020-30/07/2020
DOI: 10.1145/3397271.3401432
DOI: 10.48550/arxiv.2005.06213
Project(s): BigDataGrapes
Metrics:
See at:
arXiv.org e-Print Archive | arxiv.org | ISTI Repository | dl.acm.org | doi.org | doi.org | CNR ExploRA
2020
Journal article
Open Access
Practical trade-offs for the prefix-sum problem
Pibiri G. E., Venturini R.
Given an integer arrayA, theprefix-sum problemis to answersum(i)queries that return the sum of the elements inA[0..i], knowing that the integers inAcan be changed. It is a classic problem in data structure design with a wide range of applications in computing from coding to databases. In this work, we propose and compare practical solutions to this problem, showing that new trade-offs between the performance of queries and updates can be achieved on modern hardware.Source: Software, practice & experience (Print) (2020). doi:10.1002/spe.2918
DOI: 10.1002/spe.2918
DOI: 10.48550/arxiv.2006.14552
Project(s): BigDataGrapes
Metrics:
Pibiri G. E., Venturini R.
Given an integer arrayA, theprefix-sum problemis to answersum(i)queries that return the sum of the elements inA[0..i], knowing that the integers inAcan be changed. It is a classic problem in data structure design with a wide range of applications in computing from coding to databases. In this work, we propose and compare practical solutions to this problem, showing that new trade-offs between the performance of queries and updates can be achieved on modern hardware.Source: Software, practice & experience (Print) (2020). doi:10.1002/spe.2918
DOI: 10.1002/spe.2918
DOI: 10.48550/arxiv.2006.14552
Project(s): BigDataGrapes
Metrics:
See at:
arXiv.org e-Print Archive | Software Practice and Experience | Software Practice and Experience | doi.org | onlinelibrary.wiley.com | CNR ExploRA
2020
Journal article
Open Access
Techniques for inverted index compression
Pibiri G. E., Venturini R.
The data structure at the core of large-scale search engines is the inverted index, which is essentially a collection of sorted integer sequences called inverted lists. Because of the many documents indexed by such engines and stringent performance requirements imposed by the heavy load of queries, the inverted index stores billions of integers that must be searched efficiently. In this scenario, index compression is essential because it leads to a better exploitation of the computer memory hierarchy for faster query processing and, at the same time, allows reducing the number of storage machines. The aim of this article is twofold: first, surveying the encoding algorithms suitable for inverted index compression and, second, characterizing the performance of the inverted index through experimentation.Source: ACM computing surveys 53 (2020). doi:10.1145/3415148
DOI: 10.1145/3415148
DOI: 10.48550/arxiv.1908.10598
Project(s): BigDataGrapes
Metrics:
Pibiri G. E., Venturini R.
The data structure at the core of large-scale search engines is the inverted index, which is essentially a collection of sorted integer sequences called inverted lists. Because of the many documents indexed by such engines and stringent performance requirements imposed by the heavy load of queries, the inverted index stores billions of integers that must be searched efficiently. In this scenario, index compression is essential because it leads to a better exploitation of the computer memory hierarchy for faster query processing and, at the same time, allows reducing the number of storage machines. The aim of this article is twofold: first, surveying the encoding algorithms suitable for inverted index compression and, second, characterizing the performance of the inverted index through experimentation.Source: ACM computing surveys 53 (2020). doi:10.1145/3415148
DOI: 10.1145/3415148
DOI: 10.48550/arxiv.1908.10598
Project(s): BigDataGrapes
Metrics:
See at:
arXiv.org e-Print Archive | ACM Computing Surveys | ISTI Repository | dl.acm.org | ACM Computing Surveys | doi.org | CNR ExploRA
2019
Conference article
Open Access
Fast dictionary-based compression for inverted indexes
Pibiri G. E., Petri M., Moffat A.
Dictionary-based compression schemes provide fast decoding operation, typically at the expense of reduced compression effectiveness compared to statistical or probability-based approaches. In this work, we apply dictionary-based techniques to the compression of inverted lists, showing that the high degree of regularity that these integer sequences exhibit is a good match for certain types of dictionary methods, and that an important new trade-off balance between compression effectiveness and compression efficiency can be achieved. Our observations are supported by experiments using the document-level inverted index data for two large text collections, and a wide range of other index compression implementations as reference points. Those experiments demonstrate that the gap between efficiency and effectiveness can be substantially narrowed.Source: International Conference on Web Search and Data Mining, pp. 6–14, 11/02/2019,15/02/2019
DOI: 10.1145/3289600.3290962
Metrics:
Pibiri G. E., Petri M., Moffat A.
Dictionary-based compression schemes provide fast decoding operation, typically at the expense of reduced compression effectiveness compared to statistical or probability-based approaches. In this work, we apply dictionary-based techniques to the compression of inverted lists, showing that the high degree of regularity that these integer sequences exhibit is a good match for certain types of dictionary methods, and that an important new trade-off balance between compression effectiveness and compression efficiency can be achieved. Our observations are supported by experiments using the document-level inverted index data for two large text collections, and a wide range of other index compression implementations as reference points. Those experiments demonstrate that the gap between efficiency and effectiveness can be substantially narrowed.Source: International Conference on Web Search and Data Mining, pp. 6–14, 11/02/2019,15/02/2019
DOI: 10.1145/3289600.3290962
Metrics:
See at:
ISTI Repository | dl.acm.org | doi.org | CNR ExploRA
2019
Journal article
Open Access
Handling massive n-gram datasets efficiently
Pibiri G. E., Venturini R.
Two fundamental problems concern the handling of large n-gram language models: indexing, that is, compressing the n-grams and associated satellite values without compromising their retrieval speed, and estimation, that is, computing the probability distribution of the n-grams extracted from a large textual source. Performing these two tasks efficiently is vital for several applications in the fields of Information Retrieval, Natural Language Processing, and Machine Learning, such as auto-completion in search engines and machine translation. Regarding the problem of indexing, we describe compressed, exact, and lossless data structures that simultaneously achieve high space reductions and no time degradation with respect to the state-of-the-art solutions and related software packages. In particular, we present a compressed trie data structure in which each word of an n-gram following a context of fixed length k, that is, its preceding k words, is encoded as an integer whose value is proportional to the number of words that follow such context. Since the number of words following a given context is typically very small in natural languages, we lower the space of representation to compression levels that were never achieved before, allowing the indexing of billions of strings. Despite the significant savings in space, our technique introduces a negligible penalty at query time. Specifically, the most space-efficient competitors in the literature, which are both quantized and lossy, do not take less than our trie data structure and are up to 5 times slower. Conversely, our trie is as fast as the fastest competitor but also retains an advantage of up to 65% in absolute space. Regarding the problem of estimation, we present a novel algorithm for estimating modified Kneser-Ney language models that have emerged as the de-facto choice for language modeling in both academia and industry thanks to their relatively low perplexity performance. Estimating such models from large textual sources poses the challenge of devising algorithms that make a parsimonious use of the disk. The state-of-the-art algorithm uses three sorting steps in external memory: we show an improved construction that requires only one sorting step by exploiting the properties of the extracted n-gram strings. With an extensive experimental analysis performed on billions of n-grams, we show an average improvement of 4.5 times on the total runtime of the previous approach.Source: ACM transactions on information systems 37 (2019). doi:10.1145/3302913
DOI: 10.1145/3302913
DOI: 10.48550/arxiv.1806.09447
DOI: 10.5281/zenodo.3257994
DOI: 10.5281/zenodo.3257995
Project(s): BigDataGrapes
Metrics:
Pibiri G. E., Venturini R.
Two fundamental problems concern the handling of large n-gram language models: indexing, that is, compressing the n-grams and associated satellite values without compromising their retrieval speed, and estimation, that is, computing the probability distribution of the n-grams extracted from a large textual source. Performing these two tasks efficiently is vital for several applications in the fields of Information Retrieval, Natural Language Processing, and Machine Learning, such as auto-completion in search engines and machine translation. Regarding the problem of indexing, we describe compressed, exact, and lossless data structures that simultaneously achieve high space reductions and no time degradation with respect to the state-of-the-art solutions and related software packages. In particular, we present a compressed trie data structure in which each word of an n-gram following a context of fixed length k, that is, its preceding k words, is encoded as an integer whose value is proportional to the number of words that follow such context. Since the number of words following a given context is typically very small in natural languages, we lower the space of representation to compression levels that were never achieved before, allowing the indexing of billions of strings. Despite the significant savings in space, our technique introduces a negligible penalty at query time. Specifically, the most space-efficient competitors in the literature, which are both quantized and lossy, do not take less than our trie data structure and are up to 5 times slower. Conversely, our trie is as fast as the fastest competitor but also retains an advantage of up to 65% in absolute space. Regarding the problem of estimation, we present a novel algorithm for estimating modified Kneser-Ney language models that have emerged as the de-facto choice for language modeling in both academia and industry thanks to their relatively low perplexity performance. Estimating such models from large textual sources poses the challenge of devising algorithms that make a parsimonious use of the disk. The state-of-the-art algorithm uses three sorting steps in external memory: we show an improved construction that requires only one sorting step by exploiting the properties of the extracted n-gram strings. With an extensive experimental analysis performed on billions of n-grams, we show an average improvement of 4.5 times on the total runtime of the previous approach.Source: ACM transactions on information systems 37 (2019). doi:10.1145/3302913
DOI: 10.1145/3302913
DOI: 10.48550/arxiv.1806.09447
DOI: 10.5281/zenodo.3257994
DOI: 10.5281/zenodo.3257995
Project(s): BigDataGrapes
Metrics:
See at:
arXiv.org e-Print Archive | ZENODO | ZENODO | ISTI Repository | ACM Transactions on Information Systems | dl.acm.org | ACM Transactions on Information Systems | doi.org | CNR ExploRA